package Leetcode.链表;

/**
 * @Author: kirito
 * @Date: 2024/3/8 10:22
 * @Description:
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */

public class 排序链表 {
    /**
     * 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
     * 思路就是：用普通排序方法，然后交换元素改成交换链表节点
     *
     * 1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。
     * 寻找链表的中点可以使用快慢指针的做法，快指针每次移动2步，慢指针每次移动1步，
     * 当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
     * 2.对两个子链表分别排序。
     * 3.将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21.合并两个有序链表」的做法，
     * 将两个有序的子链表进行合并。
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        return mergeTwoLists2(list1, list2);
    }


    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        // 检查链表是否为空
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1; // 返回非空链表，如果有一个为空
        }

        // 创建新链表的头节点
        ListNode head = new ListNode(0);
        ListNode tail = head; // 用于追踪新链表的尾部
        ListNode a = list1, b = list2; // 分别追踪链表 list1 和 list2 的当前节点

        // 遍历链表 list1 和 list2，将较小的节点加入到新链表
        while (a != null && b != null) {
            if (a.val < b.val) {
                tail.next = a; // 将较小节点连接到新链表
                a = a.next; // 移动 list1 的指针到下一个节点
            } else {
                tail.next = b; // 将较小节点连接到新链表
                b = b.next; // 移动 list2 的指针到下一个节点
            }
            tail = tail.next; // 移动新链表的尾指针到刚刚添加的节点
        }

        // 将剩余的链表部分连接到新链表
        tail.next = (a != null ? a : b);

        return head.next; // 返回合并后的链表头节点
    }
}
